// https://www.lintcode.com/problem/connecting-graph/description

class ConnectingGraph {
public:
    int* father;
    /*
    * @param n: An integer
    */ConnectingGraph(int n) {
        father = new int[n + 1];
        for (int i = 1; i < n + 1; ++i)
        {
            father[i] = i;
        }
    }

    int find(int a)
    {
        int tmp = a;
        while (father[a] != a)
        {
            a = father[a];
        }
        while (tmp != a)
        {
            int tfather = father[tmp];
            father[tmp] = a;
            tmp = tfather;
        }
        return a;
    }

    /*
     * @param a: An integer
     * @param b: An integer
     * @return: nothing
     */
    void connect(int a, int b) {
        // int fa = father[a];
        // int fb = father[b];
        int fa = find(a);
        int fb = find(b);
        if (fa != fb)
        {
            father[fa] = fb;
        }
    }

    /*
     * @param a: An integer
     * @param b: An integer
     * @return: A boolean
     */
    bool query(int a, int b) {
        return find(a) == find(b);
    }
};